package com.leetcode.solution.s8x;

import com.leetcode.solution.model.ListNode;

public class Partition86 {
    public static void main(String[] args) {
        ListNode node = new Partition86().partition(createLinklist(), 3);
        while(node != null) {
            System.out.print(node.val);
            node = node.next;
        }

    }

    private static ListNode createLinklist() {
        ListNode head = new ListNode(1);
        ListNode node = head;
        node.next = new ListNode(4);
        node = node.next;

        node.next = new ListNode(3);
        node = node.next;

        node.next = new ListNode(2);
        node = node.next;

        node.next = new ListNode(5);
        node = node.next;

        node.next = new ListNode(2);

        return head;
    }

    public ListNode partition(ListNode head, int x) {
        ListNode smallHead = new ListNode(0);
        ListNode largerHead = new ListNode(0);
        ListNode small = smallHead;
        ListNode larger = largerHead;
        while (head != null) {
            if (head.val < x) {
                small.next = head;
                small = small.next;
            } else if (head.val >= x) {
                larger.next = head;
                larger = larger.next;
            }

            head = head.next;
        }

        larger.next = null;
        small.next = largerHead.next;
        return smallHead.next;
    }
}
